SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Damm algorithm</title>

</head>

Damm algorithm

</h1>

</header>

In <a href="Error_detection" class="mw-redirect" title="Error detection">error detection</a>, the Damm algorithm is a <a href="Check_digit" title="Check digit">check digit</a> <a href="Algorithm" title="Algorithm">algorithm</a> that detects all <a href="Transcription_error" title="Transcription error">single-digit errors</a> and all <a href="Transcription_error#Transposition_error" title="Transcription error">adjacent transposition errors</a>. It was presented by H. Michael Damm in 2004,<a href="#cite_note-fenwick2014-1">[1]</a> as a part of his PhD dissertation entitled Totally Antisymmetric Quasigroups.

<div class="mw-heading mw-heading2"><h2 id="Strengths_and_weaknesses">Strengths and weaknesses</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Strengths">Strengths</h3></div>

The Damm algorithm is similar to the <a href="Verhoeff_algorithm" title="Verhoeff algorithm">Verhoeff algorithm</a>. It too will detect all occurrences of the two most frequently appearing types of <a href="Transcription_error" title="Transcription error">transcription errors</a>, namely altering a single digit or transposing two adjacent digits (including the transposition of the trailing check digit and the preceding digit).<a href="#cite_note-fenwick2014-1">[1]</a><a href="#cite_note-Salomon2005-2">[2]</a> The Damm algorithm has the benefit that it does not have the dedicatedly constructed <a href="Permutation" title="Permutation">permutations</a> and its position-specific <a href="Exponentiation#In_abstract_algebra" title="Exponentiation">powers</a> of the <a href="Verhoeff_algorithm" title="Verhoeff algorithm">Verhoeff scheme</a>. A table of <a href="Inverse_element" title="Inverse element">inverses</a> can also be dispensed with when all main diagonal entries of the operation table are zero.

The Damm algorithm generates only 10 possible values, avoiding the need for a non-digit character (such as the <a href="X" title="X">X</a> in the <a href="ISBN#ISBN-10_check_digit_calculation" title="ISBN">10-digit ISBN</a> <a href="Check_digit#ISBN_10" title="Check digit">check digit</a> scheme).

Prepending leading zeros does not affect the check digit (a weakness for variable-length codes).<a href="#cite_note-fenwick2014-1">[1]</a>

There are totally anti-symmetric quasigroups that detect all phonetic errors associated with the English language (13 ↔ 30, 14 ↔ 40, ..., 19 ↔ 90). The table used in the illustrating example is based on an instance of such kind.

<div class="mw-heading mw-heading3"><h3 id="Weaknesses">Weaknesses</h3></div>

For all checksum algorithms, including the Damm algorithm, prepending leading zeroes does not affect the check digit,<a href="#cite_note-fenwick2014-1">[1]</a> so 1, 01, 001, etc. produce the same check digit. Consequently variable-length codes should not be verified together.

<div class="mw-heading mw-heading2"><h2 id="Design">Design</h2></div>

Its essential part is a <a href="Quasigroup" title="Quasigroup">quasigroup</a> of <a href="Order_(group_theory)" title="Order (group theory)">order</a> 10 (i.e. having a 10 × 10 <a href="Latin_square" title="Latin square">Latin square</a> as the body of its <a href="Cayley_table" title="Cayley table">operation table</a>) with the special feature of being <a href="Quasigroup#Total_antisymmetry" title="Quasigroup">weakly totally anti-symmetric</a>.<a href="#cite_note-dhmd-3">[3]</a><a href="#cite_note-damm2007-4">[4]</a><a href="#cite_note-BIS2003-5">[i]</a><a href="#cite_note-Chen2009-6">[ii]</a><a href="#cite_note-Mileva2009-7">[iii]</a> Damm revealed several methods to create totally anti-symmetric quasigroups of order 10 and gave some examples in his doctoral dissertation.<a href="#cite_note-dhmd-3">[3]</a><a href="#cite_note-BIS2003-5">[i]</a> With this, Damm also disproved an old conjecture that totally anti-symmetric quasigroups of order 10 do not exist.<a href="#cite_note-damm2003-8">[5]</a>

A quasigroup (Q, ∗) is called totally anti-symmetric if for all c, x, y ∈ Q, the following implications hold:<a href="#cite_note-damm2007-4">[4]</a>

and it is called weak totally anti-symmetric if only the first implication holds. Damm proved that the existence of a totally anti-symmetric quasigroup of order n is equivalent to the existence of a weak totally anti-symmetric quasigroup of order n. For the Damm algorithm with the check equation

(...((0 ∗ xm) ∗ xm−1) ∗ ...) ∗ x0 = 0,

a weak totally anti-symmetric quasigroup with the property

x ∗ x = 0

is needed. Such a quasigroup can be constructed from any totally anti-symmetric quasigroup by rearranging the columns in such a way that all zeros lay on the diagonal. And, on the other hand, from any weak totally anti-symmetric quasigroup a totally anti-symmetric quasigroup can be constructed by rearranging the columns in such a way that the first row is in natural order.<a href="#cite_note-dhmd-3">[3]</a>

<div class="mw-heading mw-heading2"><h2 id="Algorithm">Algorithm</h2></div>

The validity of a digit sequence containing a check digit is defined over a quasigroup. A quasigroup table ready for use can be taken from Damm's dissertation (pages 98, 106, 111).<a href="#cite_note-dhmd-3">[3]</a> It is useful if each main diagonal entry is 0,<a href="#cite_note-fenwick2014-1">[1]</a> because it simplifies the check digit calculation.

<div class="mw-heading mw-heading3"><h3 id="Validating_a_number_against_the_included_check_digit">Validating a number against the included check digit</h3></div>

<ol><li>Set up an interim digit and initialize it to 0.</li>

<li>Process the number digit by digit: Use the number's digit as column index and the interim digit as row index, take the table entry and replace the interim digit with it.</li>

<li>The number is valid if and only if the resulting interim digit has the value of 0.<a href="#cite_note-fenwick2014-1">[1]</a></li></ol>

<div class="mw-heading mw-heading3"><h3 id="Calculating_the_check_digit">Calculating the check digit</h3></div>

Prerequisite: The main diagonal entries of the table are 0.

<ol><li>Set up an interim digit and initialize it to 0.</li>

<li>Process the number digit by digit: Use the number's digit as column index and the interim digit as row index, take the table entry and replace the interim digit with it.</li>

<li>The resulting interim digit gives the check digit and will be appended as trailing digit to the number.<a href="#cite_note-fenwick2014-1">[1]</a></li></ol>

<div class="mw-heading mw-heading2"><h2 id="Example">Example</h2></div>

The following operation table will be used.<a href="#cite_note-fenwick2014-1">[1]</a> It may be obtained from the totally anti-symmetric quasigroup x ∗ y in Damm's doctoral dissertation page 111<a href="#cite_note-dhmd-3">[3]</a> by rearranging the rows and changing the entries with the permutation φ = (1 2 9 5 4 8 6 7 3) and defining x ⋅ y = φ−1(φ(x) ∗ y).

<td style="width:1.5em">⋅

</td>

<td style="width:1.5em">0

</td>

<td style="width:1.5em">1

</td>

<td style="width:1.5em">2

</td>

<td style="width:1.5em">3

</td>

<td style="width:1.5em">4

</td>

<td style="width:1.5em">5

</td>

<td style="width:1.5em">6

</td>

<td style="width:1.5em">7

</td>

<td style="width:1.5em">8

</td>

<td style="width:1.5em">9

</td></tr>

<tr>

<td>0

</td>

<td>2

</td></tr>

<tr>

<td>1

</td>

<td>3

</td></tr>

<tr>

<td>2

</td>

<td>9

</td></tr>

<tr>

<td>3

</td>

<td>6

</td></tr>

<tr>

<td>4

</td>

<td>8

</td></tr>

<tr>

<td>5

</td>

<td>1

</td></tr>

<tr>

<td>6

</td>

<td>4

</td></tr>

<tr>

<td>7

</td>

<td>7

</td></tr>

<tr>

<td>8

</td>

<td>5

</td></tr>

<tr>

<td>9

</td>

<td>0

</td></tr></tbody></table>

Suppose we choose the number (digit sequence) 572.

<div class="mw-heading mw-heading3"><h3 id="Calculating_the_check_digit_2">Calculating the check digit</h3></div>

<th style="color:black">digit to be processed → column index

</th>

<td style="width:1.5em">5

</td>

<td style="width:1.5em">7

</td>

<td style="width:1.5em">2

</td></tr>

<tr>

<th style="color:black">old interim digit → row index

</th>

<td>0

</td>

<td>9

</td>

<td>7

</td></tr>

<tr>

<th style="color:black">table entry → new interim digit

</th>

<td>9

</td>

<td>7

</td>

<td>4

</td></tr></tbody></table>

The resulting interim digit is 4. This is the calculated check digit. We append it to the number and obtain 5724.

<div class="mw-heading mw-heading3"><h3 id="Validating_a_number_against_the_included_check_digit_2">Validating a number against the included check digit</h3></div>

<th style="color:black">digit to be processed → column index

</th>

<td style="width:1.5em">5

</td>

<td style="width:1.5em">7

</td>

<td style="width:1.5em">2

</td>

<td style="width:1.5em">4

</td></tr>

<tr>

<th style="color:black">old interim digit → row index

</th>

<td>0

</td>

<td>9

</td>

<td>7

</td>

<td>4

</td></tr>

<tr>

<th style="color:black">table entry → new interim digit

</th>

<td>9

</td>

<td>7

</td>

<td>4

</td>

<td>0

</td></tr></tbody></table>

The resulting interim digit is 0, hence the number is valid.

<div class="mw-heading mw-heading3"><h3 id="Graphical_illustration">Graphical illustration</h3></div>

This is the above example showing the detail of the algorithm generating the check digit (dashed blue arrow) and verifying the number 572 with the check digit.

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFFenwick2014" class="citation book cs1">Fenwick, Peter (2014). "Checksums and Error Control". In Fenwick, Peter (ed.). Introduction to Computer Data Representation. Bentham Science Publishers. pp. <a rel="nofollow" class="external text" href="http://ebooks.benthamscience.com/sample/9781608058822/51/">191–218</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2174%2F9781608058822114010013">10.2174/9781608058822114010013</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-60805-883-9</bdi>.</cite>

</li>

<li id="cite_note-Salomon2005-2"><a href="#cite_ref-Salomon2005_2-0">^</a> For the types of common errors and their frequencies, see <cite id="CITEREFSalomon2005" class="citation book cs1">Salomon, David (2005). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=Zr9bjEpXKnIC&pg=PA36">Coding for Data and Computer Communications</a>. Springer Science+Business Media, Inc. p. 36. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0387-21245-6</bdi>.</cite>

</li>

<li id="cite_note-dhmd-3">^ <a href="#cite_ref-dhmd_3-0">a</a> <a href="#cite_ref-dhmd_3-1">b</a> <a href="#cite_ref-dhmd_3-2">c</a> <a href="#cite_ref-dhmd_3-3">d</a> <a href="#cite_ref-dhmd_3-4">e</a> <cite id="CITEREFDamm2004" class="citation book cs1 cs1-prop-foreign-lang-source">Damm, H. Michael (2004). <a rel="nofollow" class="external text" href="http://archiv.ub.uni-marburg.de/diss/z2004/0516/pdf/dhmd.pdf">Total anti-symmetrische Quasigruppen</a> (PDF) (Dr. rer. nat.) (in German). Philipps-Universität Marburg. <a rel="nofollow" class="external text" href="http://nbn-resolving.de/urn:nbn:de:hebis:04-z2004-05162">urn:nbn:de:hebis:04-z2004-05162</a>.</cite>

</li>

<li id="cite_note-damm2007-4">^ <a href="#cite_ref-damm2007_4-0">a</a> <a href="#cite_ref-damm2007_4-1">b</a> <cite id="CITEREFDamm2007" class="citation journal cs1">Damm, H. Michael (2007). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.disc.2006.05.033">"Totally anti-symmetric quasigroups for all orders n ≠ 2, 6"</a>. Discrete Mathematics. 307 (6): 715–729. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.disc.2006.05.033">10.1016/j.disc.2006.05.033</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0012-365X">0012-365X</a>.</cite>

</li>

<li id="cite_note-damm2003-8"><a href="#cite_ref-damm2003_8-0">^</a> <cite id="CITEREFDamm2003" class="citation journal cs1">Damm, H. Michael (2003). "On the Existence of Totally Anti-Symmetric Quasigroups of Order 4k + 2". Computing. 70 (4): 349–357. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs00607-003-0017-3">10.1007/s00607-003-0017-3</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0010-485X">0010-485X</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:31659430">31659430</a>.</cite>

</li>

</ol></div></div>

<li id="cite_note-BIS2003-5">^ <a href="#cite_ref-BIS2003_5-0">a</a> <a href="#cite_ref-BIS2003_5-1">b</a> <cite id="CITEREFBeliavscaiaIzbaşŞcerbacov2003" class="citation journal cs1">Beliavscaia, Galina; Izbaş, Vladimir; Şcerbacov, Victor (2003). <a rel="nofollow" class="external text" href="http://www.math.md/files/qrs/v10-n1/v10-n1-(pp1-28).pdf">"Check character systems over quasigroups and loops"</a> (PDF). Quasigroups and Related Systems. 10 (1): 1–28. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1561-2848">1561-2848</a>.</cite> See page 23.

</li>

<li id="cite_note-Chen2009-6"><a href="#cite_ref-Chen2009_6-0">^</a> <cite id="CITEREFChen_Jiannan2009" class="citation book cs1">Chen Jiannan (2009). <a rel="nofollow" class="external text" href="http://www.academypublisher.com/proc/iwisa09/papers/iwisa09p322.pdf">"The NP-completeness of Completing Partial anti-symmetric Latin squares"</a> (PDF). <a rel="nofollow" class="external text" href="http://www.academypublisher.com/proc/iwisa09/">Proceedings of 2009 International Workshop on Information Security and Application (IWISA 2009)</a>. Academy Publisher. pp. <a rel="nofollow" class="external text" href="http://www.academypublisher.com/proc/iwisa09/papers/iwisa09p322.htm">322–324</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-952-5726-06-0</bdi>.</cite> See page 324.

</li>

<li id="cite_note-Mileva2009-7"><a href="#cite_ref-Mileva2009_7-0">^</a> <cite id="CITEREFMilevaDimitrova2009" class="citation journal cs1">Mileva, A.; Dimitrova, V. (2009). <a rel="nofollow" class="external text" href="http://manu.edu.mk/contributions/NMBSci/Papers/2009_5_Mileva.pdf">"Quasigroups constructed from complete mappings of a group (Z2n,⊕)"</a> (PDF). Contributions, Sec. Math. Tech. Sci., MANU/MASA. XXX (1–2): 75–93. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0351-3246">0351-3246</a>.</cite> See page 78.

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .side-box{margin:4px 0;box-sizing:border-box;border:1px solid #aaa;font-size:88%;line-height:1.25em;background-color:var(--background-color-interactive-subtle,#f8f9fa);display:flow-root}.mw-parser-output .infobox .side-box{font-size:100%}.mw-parser-output .side-box-abovebelow,.mw-parser-output .side-box-text{padding:0.25em 0.9em}.mw-parser-output .side-box-image{padding:2px 0 2px 0.9em;text-align:center}.mw-parser-output .side-box-imageright{padding:2px 0.9em 2px 0;text-align:center}@media(min-width:500px){.mw-parser-output .side-box-flex{display:flex;align-items:center}.mw-parser-output .side-box-text{flex:1;min-width:0}}@media(min-width:720px){.mw-parser-output .side-box{width:238px}.mw-parser-output .side-box-right{clear:right;float:right;margin-left:1em}.mw-parser-output .side-box-left{margin-right:1em}}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1237033735">

/* start https://en.wikipedia.org/ */

@media print{body.ns-0 .mw-parser-output .sistersitebox{display:none!important}}@media screen{html.skin-theme-clientpref-night .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}

/* end https://en.wikipedia.org/ */

</style><div class="side-box side-box-right sistersitebox"><style data-mw-deduplicate="TemplateStyles:r1126788409">

/* start https://en.wikipedia.org/ */

.mw-parser-output .plainlist ol,.mw-parser-output .plainlist ul{line-height:inherit;list-style:none;margin:0;padding:0}.mw-parser-output .plainlist ol li,.mw-parser-output .plainlist ul li{margin-bottom:0}

/* end https://en.wikipedia.org/ */

</style>

<div class="side-box-text plainlist">Wikibooks has a book on the topic of: <a href="https://en.wikibooks.org/wiki/Algorithm_Implementation/Checksums/Damm_Algorithm" class="extiw external" title="wikibooks:Algorithm Implementation/Checksums/Damm Algorithm">Algorithm Implementation/Checksums/Damm Algorithm</a></div></div>

</div>

<ul><li><a href="https://en.wikibooks.org/wiki/Algorithm_Implementation/Checksums/Damm_Algorithm" class="extiw external" title="b:Algorithm Implementation/Checksums/Damm Algorithm">Damm validation & generation code in several programming languages</a></li>

<li><a rel="nofollow" class="external text" href="https://www.cantab-ip.com/blog/2014/01/20/new-format-for-singapore-ip-application-numbers-at-ipos/">Practical application in Singapore</a></li>

<li><a rel="nofollow" class="external text" href="http://www.md-software.de/math/DAMM_Quasigruppen.txt">Quasigroups for the Damm algorithm up to order 64</a></li>

<li><a rel="nofollow" class="external text" href="https://rosettacode.org/wiki/Damm_algorithm">At RosettaCode.org, Implementations of the Damm algorithm in many programming languages</a></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-06-08" href="https://en.wikipedia.org/wiki/?title=Damm_algorithm&oldid=1294493231">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>